"""
对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。

给定一个整数数组A及它的大小n，请返回最短子数组的长度。
测试样例：
[1,5,3,4,2,6,7],7
4
"""
class ShortSubsequence:
    def findShortest(self, A, n):
        i = 0
        j = n-1
        while min(A[i + 1:]) >= A[i]:
            i += 1
        while A[j] >= max(A[i:j]):
            j -= 1
        return j-i+1

def adjust_heap(ls,i,size):
    l = 2*i + 1
    r = l+1
    max = i
    if i < size/2:
        if l < size and ls[l] > ls[max]:
            max = l
        if r < size and ls[r] > ls[max]:
            max = r
        if max != i:
            ls[i], ls[max] = ls[max], ls[i]
            adjust_heap(ls,max,size)

def heap_sort(arr):
    for i in range(len(arr)//2)[::-1]:
        adjust_heap(arr,i,len(arr))
    for i in range(len(arr))[::-1]:
        arr[0],arr[i] = arr[i], arr[0]
        adjust_heap(arr,0,i)
    return arr

print(heap_sort([1,5,3,4,2,6,7]))
# s = ShortSubsequence()
# rea = s.findShortest([1,5,3,4,2,6,7],7)
# print(rea)
